Ngày 22 tháng 5 năm 1958, các nước Đông Nam Á tham dự Đại hội Thể thao châu Á lần thứ III ở Tokyo, Nhật Bản, Phó Chủ tịch Ủy ban Olympic Thái Lan khi đó là Laung Sukhumnaipradit đã đề xuất và được các nước Đông Nam Á nhất trí thành lập một tổ chức thể thao của Đông Nam Á với tên gọi ban đầu là Liên đoàn Thể thao Bán đảo Đông Nam Á (The South East Asian Peninsular Games Federation hay SEAP Games Federation). Liên đoàn Thể thao Đông Nam Á sẽ tổ chức hai năm một lần vào năm lẻ một đại hội thể thao khu vực nhằm mục đích:

1. Tăng cường tình hữu nghị, tình đoàn kết và sự hiểu biết lẫn nhau giữa các nước trong khu vực ASEAN.
2. Nâng cao không ngừng thành tích, kỹ thuật, chiến thuật các môn thể thao cho vận động viên để có cơ sở tham gia Đại hội Thể thao châu Á và Olympic.

Thái Lan, Myanmar, Malaysia, Lào, Việt Nam Cộng Hòa trước đây và Campuchia (Singapore thêm vào sau đó khi tách ra khỏi Malaysia để trở thành quốc gia độc lập vào ngày 9 tháng 5, 1965) là các nước sáng lập. Ủy ban Liên đoàn SEAP Games được thành lập vào tháng 6 năm 1959 tại Bangkok thủ đô Thái Lan. Các nước sáng lập đã thông qua điều lệ của Liên đoàn và bầu ra Ban chấp hành. Ông Prabhas Charustiara, Chủ tịch Ủy ban Olympic Quốc gia Thái Lan, được bầu làm Chủ tịch Liên đoàn Thể thao Đông Nam Á đầu tiên.

SEAP Games đầu tiên được tổ chức tại Bangkok từ 12-17 tháng 12, 1959 với hơn 527 vận động viên và quan chức thể thao đến từ Thái Lan, Miến Điện, Malaysia, Singapore, Việt Nam và Lào tham dự trong 12 môn thể thao.

Tại SEAP Games lần thứ 8 tổ chức vào năm 1975, Liên đoàn SEAP đã xem xét kết nạp thêm Indonesia và Philippines. Hai nước này chính thức được kết nạp năm 1977, cùng năm đó Liên đoàn SEAP đổi tên thành Liên đoàn Thể thao Đông Nam Á (South East Asian Games Federation, SEAGF), và sự kiện thể thao này cũng đổi tên theo thành Đại hội Thể thao Đông Nam Á. Brunei được kết nạp vào SEA Games thứ 10 tại Jakarta, Indonesia, và Đông Timor được kết nạp tại SEA Games thứ 22 tại Hà Nội, Việt Nam.

Tính đến thời điểm này, Thái Lan và Malaysia là hai quốc gia có số lần tổ chức Đại hội Thể thao Đông Nam Á nhiều nhất với sáu lần. Singapore, Indonesia và Philippines xếp thứ hai với bốn lần tổ chức Đại hội Thể thao Đông Nam Á. Myanmar xếp thứ ba với ba lần tổ chức Đại hội Thể thao Đông Nam Á. Những quốc gia có một lần tổ chức bao gồm: Việt Nam, Brunei, Lào và Campuchia.